package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/30 22:44<br>
 */
public class 鸡蛋掉落 {
    public int superEggDrop(int k, int n) {
        // only one egg situation
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; ++i) {
            dp[i] = i;
        }

        // two and more eggs
        for (int j = 2; j <= k; ++j) {
            int[] dp2 = new int[n + 1];
            // start from floor 1
            int x = 1;
            for (int i = 1; i <= n; ++i) {
                // start to calculate from bottom
                // Notice max(dp[x-1], dp2[n-x]) > max(dp[x], dp2[n-x-1])
                // is simply max(T1(x-1), T2(x-1)) > max(T1(x), T2(x)).
                while (x < i && Math.max(dp[x - 1], dp2[i - x]) > Math.max(dp[x], dp2[i - x - 1])) {
                    x++;
                }

                // The final answer happens at this x.
                dp2[i] = 1 + Math.max(dp[x - 1], dp2[i - x]);
            }
            dp = dp2;
        }

        return dp[n];
    }
}
